The present invention relates to processing digital data such as video data or image data, and more particularly, to scanning methods of transform-based digital data processing that refer to characteristics information to conditionally adjust the scan order used for encoding/decoding data blocks and related apparatus thereof.
Transform-based digital data processing is generally employed in an encoder to compress/encode video data/image data to be transmitted, and also employed in a decoder to decompress/decode the compressed/encoded data generated from the encoder. Taking MPEG-4 or H.264 standard for example, a discrete cosine transform (DCT) is involved in encoding data to be transmitted, and an inverse discrete cosine transform (IDCT) is involved in decoding encoded data. FIG. 1 is a simplified block diagram illustrating an encoder according to the related art. The conventional encoder 100 includes a DCT coder 102, a quantizer 104, a scan unit 106, and an entropy encoder 108. The DCT coder 102 receives digital data (e.g., video data or image data), and then transforms the digital data in a spatial domain into transform coefficients in a frequency domain. The quantizer 104 then quantizes the transform coefficients (i.e., DCT coefficients) to generate quantized transform coefficients. In general, the encoder 100 processes the digital data block by block. Therefore, the scan unit 106 is implemented to use a predetermined scan order to convert the two-dimensional data obtained through the preceding circuit into one-dimensional data passed to the following circuit for further processing, such as entropy encoding and/or quantization in encoding process, or entropy decoding and/or inverse-quantization in decoding process. A well-known zigzag scan order is commonly used for scanning the quantized transform coefficients (i.e., quantized DCT coefficients) at different positions in each data block. Please refer to FIG. 2, which illustrates certain exemplary conventional zigzag scan orders for a frame coded block with a block size of 4×4, a frame coded block with a block size of 8×8, a field coded block with a block size of 4×4, and a field coded block with a blocksize of 8×8, respectively.
After receiving the scan output from the scan unit 106, the entropy encoder 108 generates a bitstream through a run-level encoding scheme and variable-length coding. The run-level encoding is to encode each non-zero coefficient as a (run, level) pair, where “run” represents the number of zeros between a previous non-zero coefficient and a current non-zero coefficient, and “level” represents the value of the current non-zero coefficient. For example, assuming that a data sequence includes following values: 0, 3, 0, 1, −1, −1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, the (run, level) pairs of the exemplary data sequence are (1,3), (1,1), (0,−1), (0,−1), and (1,1). Each of the derived (run, level) pairs is then encoded using a variable-length code.
FIG. 3 is a simplified block diagram illustrating a decoder according to the related art. The conventional decoder 200 includes an entropy decoder 202, an inverse scan unit 204, an inverse quantizer 206, and an IDCT decoder 208. The decoder 200 is to reverse the operations performed by the encoder 100. The entropy decoder 202 decodes the bitstream generated from the encoder 100 into (run, level) pairs for each data block, and then outputs a sequence consisting of zero values and non-zero values according to the (run, level) pairs. Next, the inverse scan unit 204 restores two-dimensional data blocks of quantized DCT coefficients according to the same zigzag scan order employed in the encoder 100. These two-dimensional data blocks are input to the inverse quantizer 206, and the an output of the inverse quantizer 206 is inverse transformed in the IDCT decoder 208 to generate reproduced digital data.
As mentioned above, the quantized coefficients at different positions in a data block are scanned according to the selected zigzag scan order. The result of the (run, level) pairs highly depends on the zigzag scan order used for scanning the quantized coefficients. Therefore, the coding performance is related to the employed scan order. The same zigzag scan order might not be efficient for coding all of the data blocks in the raw digital data. Using a fixed scan order would therefore result in poor coding performance.